package com.example.springboottest.example.sort;

/**
 * 希尔排序,时间复杂度 O(n²)   相当于直接插入排序的升级！！！
 * 之前的查询时间复杂度都是，时间复杂度 O(n²),希尔排序是第一批突破这个时间的
 * 1、增量序列的选择。
 * Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：
 * a.最后一个增量必须为1。
 * b.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
 * 有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。
 *
 * 2、Shell排序的时间性能优于直接插入排序。
 * 希尔排序的时间性能优于直接排序的原因如下：
 * a.当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。
 * b.当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。
 * c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。
 *
 * 3、稳定性
 * 希尔排序是不稳定的。
 */
public class ShellSort extends SortBase {
    public static void main(String[] args) {
        ShellSort sort = new ShellSort();
        sort.sort(sort.dataArr);
        sort.show(sort.dataArr);
    }

    @Override
    public void sort(int[] dataArr) {
        int j;
        int swapCount = 0;
        for (int gap = dataArr.length / 2; gap > 0; gap /= 2) {
            show(dataArr);
            System.out.println("增长序列：" + gap + " :");
            for (int i = gap; i < dataArr.length; i++) {
                int temp = dataArr[i];
                for (j = i; j >= gap && temp < dataArr[j - gap]; j -= gap) {
                    dataArr[j] = dataArr[j - gap];
//                    show(dataArr);
                }
                dataArr[j] = temp;
                show(dataArr);
            }
        }
        System.out.println("希尔排序完成，共进行\t" + swapCount + "次交换");
    }
}
